package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
解析:
利用分治法，根据在搜索二叉树性质
* 若左子树不空，节点值大于左子树所有节点值；若右子树不空，小于右子树所有节点值
* 左右子树也是BST

可以拆解为，每个节点值在一定范围内，如果每个节点都符合在其范围之内，则返回true
时间复杂度O(N),每个结点访问一次
空间复杂度O(N)
https://www.youtube.com/watch?v=DYNiCaKHneY&t=311s
*/

func isValidBST(root *TreeNode) bool {
	INT_MIN := -1 << 31
	INT_MAX := 1<<31 - 1
	return helper(root, INT_MIN, INT_MAX)
}

//前序遍历
func helper(root *TreeNode, min int, max int) bool {
	if root == nil {
		return true
	}

	if root.Val > max || root.Val < min {
		return false
	}

	left := helper(root.Left, min, root.Val-1)
	right := helper(root.Right, root.Val+1, max)
	return left && right
}

/*
var prev int = -1 << 31
func isValidBST(root *TreeNode) bool {
	return helper(root)
}

//中序遍历，前一个节点的值需要小于后一个节点值，否则返回false
func helper(root *TreeNode) bool {
	if root == nil {
		return true
	}

	if helper(root.Left) {
		if root.Val > prev {
			prev = root.Val
			return helper(root.Right)
		}
	}
	return false
}
*/

func main() {
	r := TreeNode{Val: 0, Left: nil, Right: nil}
	//l := TreeNode{Val: -2, Left: nil, Right: nil}
	//r.Left = &l
	fmt.Println(isValidBST(&r))
}
